package ACwing.P4Math.Prime;

import java.util.Scanner;

/**
 * @Date : 2023-03-16
 * @Description:868. 筛质数   埃氏筛法
 * 时间复杂度， n(1/2+1/3+1/4+……+1/n)调和级数  nlnn+c
 * 1~n中有n/lnn 个质数，优化后约o(n)
 * 线性筛法》埃氏筛法》朴素算法
 */
public class SievePrime {
    static int N=1000010;
    static int cnt;
    static int[] primes=new int[N];  //素数列
    static boolean [] st=new  boolean[N]; //是否筛过
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        get_prime(n);
        System.out.println(cnt);
    }
//    朴素法(所有数的倍数都删掉)
    static void get_prime1(int n){
        for (int i = 2; i <= n; i++) {
            if(!st[i]){  //在  2~i1一定没有i的约数
                primes[cnt++]=i;  //当前数没有被筛过，则是一个质数
            }
            for (int j = i; j <=n; j+=i) st[j]=true;//倍数不是质数
        }
    }
//    埃氏筛法(所有**质数**的倍数删掉) 从i*i开始
        static void get_prime2(int n){
        for (int i = 2; i <= n; i++) {
            if(!st[i]){  //在  2~i1一定没有i的约数
                primes[cnt++]=i;  //当前数没有被筛过，则是一个质数
                   for (int j = i*i; j <=n; j+=i) st[j]=true;//倍数不是质数
            }
        }
    }
    /*也叫欧拉筛，在埃氏筛的思想下，想办法让每个合数只被筛出去一次，消除重复筛选，这样时间复杂度就能降低到O ( n )

为了让每个合数a 只被筛出去一次，由于我们是从小到大筛选质数的，因此可以考虑让这个合数a = a 1 ⋅ a 2 ⋅ . . . ⋅ a k由其最小的质因数a 1筛掉。

因此每次遍历到一个数i，不论是质数或者合数，其最小质因数如果是r，那么由于我们从小到大筛到了i，所以质数r一定已经在目前的质数结果集里了（被筛好了）。

进而，所有< r的质数都已经被筛好了，我们可以对于每个<=r的质数x，把x*i筛掉，那么因为x*i的最小质因数一定是x，所以理应在（且仅在）这一轮被筛掉。

然而，知道每个数i的最小质因数r是困难的，但反正我们都要拿它每个< = r的质数x，去筛掉x*i了，每次筛掉之后看一下质数x是不是i的因数就可以了，

因为我们是从小到大遍历质数x的，所以x第一次成为i的因数的时候，x就是i的最小质因数，这时候就可以停止筛了。

如果没有停止筛会有什么问题？重复筛选导致的算法退化！试想应在x是i的因子时停止，最后一轮筛掉的就是x*i，如果没有停下来，又取了下一个质数x ′

 ，筛掉了x ′*i
因为i的最小质因数就是x ，所以x ′ *i应该先前就被质数x以x*(i*x')/x的模式筛选过了
′
写法上应该注意，线性筛不是像埃氏筛那样，只在发现质数的轮次筛合数，而是在每个轮次i，
不管最小质因数是r的当前轮次i是不是质数，都用< = r 的所有质数x去筛x*i以保证每个数都仅被其最小质因数筛掉。


*/
static void get_prime(int n){
    for (int i = 2; i <= n; i++) {
        if(!st[i]){  //在  2~i1一定没有i的约数
            primes[cnt++]=i;  //当前数没有被筛过，则是一个质数
        }
                for (int j = 0; primes[j] <=n/i; j++) {  //最多筛到n
                    st[primes[j]*i]=true;  // 把合数 primes[j] * i 筛了
                    if(i%primes[j]==0) break;
                    //i%pj==0   pj一定是i的最小质因子，pj一定是pj*i的最小质因子
                    //i%pj!=0  pj一定小于i的最小质因子，pj也一定是pj*i的最小质因子
                    //只要i % pr[j] == 0说明他是pr[j]*i的  ‘最小质因数’ 了,然后结束循环，
                    //如果不break循环的话就会进行pr[j+1]*i晒掉，因为pr[j+1]*i的最小质因数
                    //不是pr[j+1],所以会导致重复删除，这也是线性筛的优点所在
                    //例如：st[2*4=8]标记之后，如果你不在下面判断if(4%2==0)break掉
                    //就会继续pr[(j+1)]*i== st[3*4=12],3不是12的最小质因数，所以这样也是
                    //会导致重复删除，执行到i=6时候，st[2*6=12]会再次标记，这样也就在此导致重复了

                    //i % pr[j] != 0 说明pr[j]永远是pr[j]*i的最小质因数
                    //因为pr[j]的最小质因数是本身pr[j]，然后pr[j]*i是pr[j]的倍数
                    //所以pr[j]*i的最小质因数也是pr[j]，永远都是，pr[j+1]*i的时候也是

                }
            }
            //优化，只需要把质数的倍数删掉
        }
    }

